import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-09-09
 * Time:23:43
 */

/***
 * 力扣496:下一个更大元素Ⅰ
 */

//单调栈 + 哈希表
public class nextGreaterElement {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //建立哈希表
        Map<Integer, Integer> map = new HashMap<>();
        //建立栈
        Deque<Integer> stack = new ArrayDeque<>();
        //对nums2从后向前遍历存入栈中,在向前遍历时出现比栈中大的元素栈中元素出栈,更大的元素入栈,小的直接入栈
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            //当栈中非空且此时的元素大于栈中元素时栈中元素初栈
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
